home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / edit / tde40.zip / sort.c < prev    next >
C/C++ Source or Header  |  1994-06-05  |  25KB  |  739 lines
  1. /*
  2.  * These functions sort lines according to keys in a marked BOX block.
  3.  *
  4.  * Being that the data structure was changed from a big text buffer to a
  5.  * linked list, we can replace the simple insertion sort algorithm with a
  6.  * much faster sort algorithm.  The classic search and sort reference is by
  7.  * Donald E. Knuth, _The Art of Computer Programming; Volume 3:  Sorting and
  8.  * Searching_.  One of the fastest and most widely used general purpose
  9.  * sorting algorithms is the "Quicksort" algorithm.
  10.  *
  11.  * For implementation hints and guidelines on the Quicksort algorithm, one
  12.  * might read the original Quicksort paper by C. A. R. Hoare or anything
  13.  * by Robert Sedgewick.  Although Dr. Sedgewick includes a chapter on
  14.  * Quicksort in his intro computer science textbooks, _Algorithms in X_,
  15.  * I prefer the detailed hints and guidelines in his 1978 CACM paper.
  16.  * Incidentally, Dr. Sedgewick's Ph.D. dissertation was on the modification
  17.  * and mathematical analysis of the Quicksort algorithm.
  18.  *
  19.  *
  20.  * See:
  21.  *
  22.  *   Charles Antony Richard Hoare, "Algorithm 63: Partition."  _Communications
  23.  *      of the ACM_, 4 (No. 7): 321, 1961.
  24.  *
  25.  *   Charles Antony Richard Hoare, "Algorithm 64: Quicksort."  _Communications
  26.  *      of the ACM_, 4 (No. 7): 321, 1961.
  27.  *
  28.  *   Charles Antony Richard Hoare, "Quicksort."  _The Computer Journal_,
  29.  *      5 (April 1962 - January 1963): 10-15, 1962.
  30.  *
  31.  * See also:
  32.  *
  33.  *   Donald Ervin Knuth, _The Art of Computer Programming; Volume 3:  Sorting
  34.  *     and Searching_, Addison-Wesley, Reading, Mass., 1973, Chapter 5,
  35.  *     Sorting, pp 114-123.  ISBN 0-201-03803-X.
  36.  *
  37.  *   Robert Sedgewick, "Implementing Quicksort Programs."  _Communications
  38.  *      of the ACM_, 21 (No. 10): 847-857, 1978.
  39.  *
  40.  *
  41.  *                           Quicksort in TDE
  42.  *
  43.  * Quicksort in TDE is a stable, non-recursive implementation based on
  44.  * Program 2, page 851, CACM, 21 (No. 10), 1978, by Robert Sedgewick.  My
  45.  * partition algorithm finds the median-of-three.  Then, it walks from the
  46.  * head of the list, comparing nodes, and uses the first occurrence of the
  47.  * key of the median-of-three as the partition node.  Mostly by accident
  48.  * and partly by design, my partition routine uses a "fat pivot" to keep
  49.  * equal nodes in the same relative order as they appear in the file (the
  50.  * definition of a stable sort).  By using the first median-of-three node
  51.  * as the partitioning node, 1) sorting a sorted list is fairly fast and
  52.  * 2) encountering a worst case is very unlikely.  TDE will sort, fairly
  53.  * fast, multiple keys ascending or descending, ignore or match case, and
  54.  * preserve order in the file, while using a custom sort sequence for your
  55.  * favorite domestic or foreign language.
  56.  *
  57.  * Found an error in the comparison function in versions 2.2 & 3.0.  Equal
  58.  * keys were not compared correctly.  Fixed in version 3.1.
  59.  *
  60.  * New editor name:  TDE, the Thomson-Davis Editor.
  61.  * Author:           Frank Davis
  62.  * Date:             June 5, 1991, version 1.0
  63.  * Date:             July 29, 1991, version 1.1
  64.  * Date:             October 5, 1991, version 1.2
  65.  * Date:             January 20, 1992, version 1.3
  66.  * Date:             February 17, 1992, version 1.4
  67.  * Date:             April 1, 1992, version 1.5
  68.  * Date:             June 5, 1992, version 2.0
  69.  * Date:             October 31, 1992, version 2.1
  70.  * Date:             April 1, 1993, version 2.2
  71.  * Date:             June 5, 1993, version 3.0
  72.  * Date:             August 29, 1993, version 3.1
  73.  * Date:             November 13, 1993, version 3.2
  74.  * Date:             June 5, 1994, version 4.0
  75.  *
  76.  * This code is released into the public domain, Frank Davis.
  77.  * You may use and distribute it freely.
  78.  */
  79.  
  80. #include "tdestr.h"
  81. #include "common.h"
  82. #include "tdefunc.h"
  83. #include "define.h"
  84.  
  85.  
  86. /*
  87.  * Name:    sort_box_block
  88.  * Purpose: sort lines according to text in marked BOX block
  89.  * Date:    June 5, 1992
  90.  * Passed:  window:  pointer to current window
  91.  * Notes:   quick sort and insertion sort the lines in the BOX buff according
  92.  *           to stuff in a box block.
  93.  */
  94. int  sort_box_block( TDE_WIN *window )
  95. {
  96. int  prompt_line;
  97. int  block_type;
  98. line_list_ptr ll;
  99. register file_infos *file;
  100. TDE_WIN *sw;
  101. int  rc;
  102. #if defined( __UNIX__ )
  103.  chtype display_buff[MAX_COLS+2];       /* chtype is defined in curses.h */
  104. #else
  105.  char display_buff[(MAX_COLS+2)*2];
  106. #endif
  107.  
  108.    /*
  109.     * make sure block is marked OK
  110.     */
  111.    rc = OK;
  112.    prompt_line = window->bottom_line;
  113.    entab_linebuff( );
  114.    if (un_copy_line( window->ll, window, TRUE ) == ERROR)
  115.       return( ERROR );
  116.    check_block( );
  117.    if (g_status.marked == TRUE) {
  118.       file  = g_status.marked_file;
  119.       block_type = file->block_type;
  120.       if (block_type == BOX) {
  121.          /*
  122.           * sort ascending or descending?
  123.           */
  124.          rc = get_sort_order( window );
  125.          if (rc != ERROR) {
  126.             file->modified = TRUE;
  127.             if (mode.do_backups == TRUE) {
  128.                sw = g_status.window_list;
  129.                for (; ptoul( sw->file_info ) != ptoul( file );)
  130.                   sw = sw->next;
  131.                backup_file( sw );
  132.             }
  133.  
  134.             /*
  135.              * figure the width of the block.
  136.              */
  137.             sort.block_len = file->block_ec + 1 - file->block_bc;
  138.  
  139.             /*
  140.              * save the prompt line and print the quicksort message.
  141.              */
  142.             save_screen_line( 0, prompt_line, display_buff );
  143.             eol_clear( 0, prompt_line, g_display.text_color );
  144.             set_prompt( block22a, prompt_line );
  145.  
  146.             /*
  147.              * set up the sort structure.
  148.              */
  149.             sort.bc  = g_status.marked_file->block_bc;
  150.             sort.ec  = g_status.marked_file->block_ec;
  151.             sort.order_array = (mode.search_case == IGNORE) ?
  152.                                     sort_order.ignore : sort_order.match;
  153.  
  154.             /*
  155.              * save the previous node for use with insertion sort.
  156.              */
  157.             ll = file->block_start->prev;
  158.             quick_sort_block( file->block_br, file->block_er,
  159.                               file->block_start, file->block_end );
  160.  
  161.             /*
  162.              * get back previous node and clean up list with insertion
  163.              *   sort.
  164.              */
  165.             if (ll == NULL)
  166.                ll = file->line_list;
  167.             else
  168.                ll = ll->next;
  169.             set_prompt( block22b, prompt_line );
  170.             insertion_sort_block( file->block_br, file->block_er, ll );
  171.  
  172.             /*
  173.              * housekeeping.  mark the file as dirty and restore the
  174.              *   cursors, which are scrambled during the sort.
  175.              */
  176.             file->dirty = GLOBAL;
  177.             restore_cursors( file );
  178.             restore_screen_line( 0, prompt_line, display_buff );
  179.          }
  180.       } else {
  181.          /*
  182.           * can only sort box blocks
  183.           */
  184.          error( WARNING, prompt_line, block23 );
  185.          rc = ERROR;
  186.       }
  187.    } else {
  188.       /*
  189.        * box not marked
  190.        */
  191.       error( WARNING, prompt_line, block24 );
  192.       rc = ERROR;
  193.    }
  194.    return( rc );
  195. }
  196.  
  197.  
  198. /*
  199.  * Name:    quick_sort_block
  200.  * Purpose: sort lines according to text in marked BOX block
  201.  * Date:    Jaunary 10, 1993
  202.  * Passed:  low:        starting line in box block
  203.  *          high:       ending line in a box block
  204.  *          low_node:   starting node in box block
  205.  *          high_node:  ending node in box block
  206.  * Notes:   Quicksort lines in the BOX block according to keys in
  207.  *           a box block.
  208.  *          because the median of three method is used to find the partion
  209.  *           node,  high - low  should be greater than or equal to 2.
  210.  *          with end recursion removal and sorting the smallest sublist
  211.  *           first, our stack only needs room for log2 (N+1)/(M+2) nodes.
  212.  *           a stack size of 24 can reliably handle almost 500 million lines.
  213.  */
  214. void quick_sort_block( long low, long high, line_list_ptr low_node,
  215.                        line_list_